class countDigitOne {
    //超时！！！
//    public int countDigitOne(int n) {
//        //计算小于等于n的非负整数中有多少个1
//        int count = 0;
//        for (int i = 1; i <= n; i++) {
//            int temp = i;
//            while (temp > 0) {
//                if (temp % 10 == 1) {
//                    count++;
//                }
//                temp /= 10;
//            }
//        }
//        return count;
//    }
    /**
     * 计算从1到n的所有整数中，数字1出现的总次数
     *
     * @param n 给定的正整数，表示计算范围的上限
     * @return 返回数字1出现的总次数
     */
    public int countDigitOne(int n) {
        // 初始化当前位数为1，用于后续的迭代计算
        int digit = 1;
        // 初始化结果变量为0，用于累计数字1出现的总次数
        int res = 0;

        // 初始化高位、当前位和低位的值
        // 高位为当前考察位以上的部分，当前位为当前考察的位，低位为当前考察位以下的部分
        int high = n / 10, cur = n % 10, low = 0;

        // 当高位或当前位不为0时，继续循环计算
        while (high != 0 || cur != 0) {
            // 当前位为0时，计算此位上1出现的次数
            if (cur == 0) {
                res += high * digit;
            }
            // 当前位为1时，计算此位上1出现的次数
            else if (cur == 1) {
                res += high * digit + low + 1;
            }
            // 当前位为2到9时，计算此位上1出现的次数
            else {
                res += (high + 1) * digit;
            }

            // 更新低位、当前位和高位的值，准备下一轮迭代
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }

        // 返回累计的数字1出现的总次数
        return res;
    }
}